package com.li.algorithm.leetcode.hot100;

import java.util.Arrays;

public class Test16 {

    public int[] productExceptSelf(int[] nums) {
        int sum = 1;
        int zero = 0;
        int[] ans = new int[nums.length];
        for (int num : nums) {
            if (num == 0) {
                zero++;
                continue;
            }
            sum *=num;
        }
        //TODO:需要处理 负数 和 零 的情况
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0 && zero != 0) {
                ans[i] = 0;
                continue;
            }
            if (nums[i] == 0 && zero != 1) {
                ans[i] = 0;
                continue;
            } else if (nums[i] == 0 && zero == 1) {
                ans[i] = sum;
                continue;
            }
            ans[i] = sum / nums[i];
        }
        return ans;
    }

    public int[] productExceptSelf2(int[] nums) {
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        int[] ans = new int[nums.length];

        //先求每个位置左边的乘积
        left[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            left[i] = left[i-1] * nums[i-1];
        }

        //再求每个位置右边的乘积
        right[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        //最后每个位置的乘积 = 左边乘积 * 右边乘积
        for (int i = 0; i < nums.length; i++) {
            ans[i] = left[i] * right[i];
        }
        return ans;
    }

    public int[] productExceptSelf3(int[] nums) {
        int[] ans = new int[nums.length];
        //先求每个位置左边的乘积
        ans[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            ans[i] = ans[i-1] * nums[i-1];
        }
        //每个位置已求出的左边的乘积 * 计算每个位置右边的乘积
        int temp = 1; // 用temp存储右边的累计乘积
        for (int i = nums.length - 2; i >= 0; i--) {
            temp = temp * nums[i + 1];
            ans[i] = ans[i] * temp;
        }
        return ans;
    }


    public static void main(String[] args) {
        Test16 test16 = new Test16();
        int[] result = test16.productExceptSelf3(new int[]{-1,1,0,-3,3});
        System.out.println(Arrays.toString(result));
    }
}
